#include <stdio.h>
#include "queue.h"
void queue_append (queue_t **ppHead, queue_t *pElem)
{
	// ppHead � o ponteiro para o ponteiro do elemento na cabe�a da fila
	// pElem � o ponteiro para o elemento a ser inserido

	// ppHead == NULL significa fila inv�lida
	// pElem == NULL significa elemento inv�lido
    if (ppHead == NULL || pElem == NULL)
        return;

    if (pElem->next != NULL || pElem->prev != NULL)
    	return;

    // pHead aponta para o elemento que � cabe�a da fila
    queue_t * pHead = * ppHead;
    queue_t * pAux;
    if (pHead == NULL) {
        // fila vazia, inserir primeiro elemento
        pHead = pElem;
        pHead->prev = pElem;
        pHead->next = pElem;
    } else {
        // fila j� possui elementos, inserir elemento novo no final
        pAux= pHead->prev; // pAux aponta para o �ltimo elemento
        pAux->next = pElem;
        pHead->prev = pElem;
        pElem->next = pHead;
        pElem->prev = pAux;
    }
    *ppHead = pHead;
    return;
}

//------------------------------------------------------------------------------
// Remove o elemento indicado da fila, sem o destruir.
// Condicoes a verificar, gerando msgs de erro:
// - a fila deve existir
// - a fila nao deve estar vazia
// - o elemento deve existir
// - o elemento deve pertencer a fila indicada
// Retorno: apontador para o elemento removido, ou NULL se erro

queue_t *queue_remove (queue_t **ppHead, queue_t *pElem)
{

	queue_t * pHead;// ponteiro para a cabe�a da fila
	queue_t * pAux;

	// se a fila existir,
    if (ppHead == NULL) {
    	return NULL;
    }
    // a cabe�a da fila tem o valor apontado por * ppHead
    pHead = *ppHead;

    // testar se pHead � nulo ou se pElem � nulo
    if ( pHead == NULL || pElem == NULL ) {
    	return NULL;
    }

    if (pHead == pElem){
    	// temos uma fila e estamos removendo a cabe�a da fila
    	// a nova cabe�a da fila ser� o pr�ximo elemento ap�s a cabe�a atual

    	if (pElem->next == pElem) {
    		// caso em que a fila s� tem um elemento
    		*ppHead = NULL;
    	} else {
			// alterar *ppHead para ser a nova cabe�a e pElem � a antiga cabe�a
			*ppHead = pHead->next;

			// o �ltimo elemento da fila aponta para a nova cabe�a
			pElem->prev->next = pElem->next; //pElem->prev aponta para o �ltimo elemento

			// a nova cabe�a tem seu campo prev atualizado
			pElem->next->prev = pElem->prev;
    	}
    	// o elemento removido n�o aponta para ningu�m
    	pElem->next = NULL;
    	pElem->prev = NULL;

    	// opera��es terminadas, retornar valor do endere�o de pElem
    	return pElem;
    }

	// se chegou aqui, estamos removendo um elemento que n�o � a cabe�a da fila
    // primeiro verificar se pElem aponta para um elemento da fila

    pAux = pHead;
    do {
    	pAux = pAux->next;
    } while ( pAux != pElem && pAux != pHead );

    if (pAux == pHead) {
    	// n�o achou pElem na fila
    	return NULL;
    }

    // pElem->next->prev apontava antes para o elemento a ser removido e agora
    // aponta para o elemento anterior a ele (pElem->prev)
    pElem->next->prev = pElem->prev;
    // pElem->prev->next apontava antes para o elemento a ser removido e agora
    // aponta para o elemento seguinte (pElem->next)
    pElem->prev->next = pElem->next;

    //o elemento removido n�o aponta para ningu�m
    pElem->prev = NULL;
    pElem->next = NULL;

    return pElem;
}

//------------------------------------------------------------------------------
// Conta o numero de elementos na fila
// Retorno: numero de elementos na fila

int queue_size (queue_t *pHead)
{
	// pHead aponta para o primeiro elemento da fila

	int size = 1;
	queue_t *pAux;
    // teste de fila vazia
	if (pHead == NULL) {
		return 0;
	}
	pAux = pHead->next;
	while (pAux != pHead){
		pAux = pAux->next;
		size++;
	}
	return size;
}

//------------------------------------------------------------------------------
// Percorre a fila e imprime na tela seu conte�do. A impress�o de cada
// elemento � feita por uma fun��o externa, definida pelo programa que
// usa a biblioteca. Essa fun��o deve ter o seguinte prot�tipo:
//
// void print_elem (void *ptr) ; // ptr aponta para o elemento a imprimir

void queue_print (char *name, queue_t *queue, void print_elem (void*) )
{
	printf("%s\n",name);
	if (queue == NULL) {
		printf("[]\n");
		return;
	}
	if (print_elem == NULL)
		return;

	queue_t * pHead = queue;
	queue_t * pAux = queue;
	printf("[");
	do {
		print_elem(pAux);
		printf(" ");
		pAux = pAux->next;
	} while (pAux != pHead);
	printf("]\n");
    return;
}
